package com.zto.sch.advance.algorithms.book.grokking;


import cn.hutool.core.util.ArrayUtil;
import com.zto.sch.base.util.CommonUtil;
import org.junit.Assert;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

/**
 * @program: sch-diy-parent
 * @description:
 * @author: sch
 * @create: 2021-07-28 21:27
 **/
public class 快速排序 {
    public static void main(String[] args) {
        int[] beforeArr = CommonUtil.randomCommonArr(1, 50, 10);
        System.out.println("排序前:" + ArrayUtil.toString(beforeArr));

        //快速排序
        Integer[] beforeArr2 = new Integer[beforeArr.length];
        for (int i = 0; i < beforeArr.length; i++) {
            beforeArr2[i] = beforeArr[i];
        }
        Integer[] afterArr = quickSort(beforeArr2);
        System.out.println("排序前:" + ArrayUtil.toString(afterArr));
    }

    /**
     * 思路：归纳证明+D&C(分而治之)
     * 1，找出基准值
     * 2，找出基准值左测数据，组成一个数组
     * 3，找出基准值右测数据，组成一个数组
     * 4，quickSort(左测数组)+基准值+quickSort(右测数组)
     *
     * @param beforeArr
     * @return
     */
    private static Integer[] quickSort(Integer[] beforeArr) {
        if (beforeArr.length < 2) {
            return beforeArr;
        }
        //1，基准值
        int baseNum = beforeArr[0];

        //2，左测数组
        List<Integer> leftList = new ArrayList();
        int count = 0;
        for (int i = 0; i < beforeArr.length; i++) {
            if (beforeArr[i] < baseNum) {
                leftList.add(beforeArr[i]);
                count++;
            }
        }
        count = 0;

        //3，右测数组
        List<Integer> rightList = new ArrayList();
        for (int i = 0; i < beforeArr.length; i++) {
            if (beforeArr[i] > baseNum) {
                rightList.add(beforeArr[i]);
                count++;
            }
        }


        //4，递归返回
        Integer[] baseArr = {baseNum};

        return ArrayUtil.addAll(quickSort(ArrayUtil.toArray(leftList, Integer.class)), baseArr, quickSort(ArrayUtil.toArray(rightList, Integer.class)));
    }
}
